package com.c2b.algorithm.newcoder.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">二叉树的最大深度</a>
 * <p>
 * 求给定二叉树的最大深度，深度是指树的根节点到任一叶子节点路径上节点的数量。最大深度是所有叶子节点的深度的最大值。（注：叶子节点是指没有子节点的节点。）
 * </p>
 * <p>
 * 数据范围：0≤n≤100000，树上每个节点的val满足∣val∣≤100<br>
 * 要求： 空间复杂度O(1),时间复杂度O(n)
 * </p>
 *
 * @author c2b
 * @since 2023/3/14 10:57
 */
public class BM0028MaxDepth_S {
    /**
     * 层次遍历（扩展思路）
     * <p>
     * step 1：既然是层次遍历，我们遍历完一层要怎么进入下一层，可以用队列记录这一层中节点的子节点。队列类似栈，只不过是一个先进先出的数据结构，可以理解为我们平时的食堂打饭的排队。因为每层都是按照从左到右开始访问的，那自然记录的子节点也是从左到右，那我们从队列出来的时候也是从左到右，完美契合。<br>
     * step 2：在刚刚进入某一层的时候，队列中的元素个数就是当前层的节点数。比如第一层，根节点先入队，队列中只有一个节点，对应第一层只有一个节点，第一层访问结束后，它的子节点刚好都加入了队列，此时队列中的元素个数就是下一层的节点数。因此遍历的时候，每层开始统计该层个数，然后遍历相应节点数，精准进入下一层。<br>
     * step 3：遍历完一层就可以节点深度就可以加1，直到遍历结束，即可得到最大深度。<br>
     * </p>
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode currLevelLastNode = root;
        TreeNode nextLevelLastNode = null;
        int maxDepth = 0;
        while (!queue.isEmpty()) {
            final TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
                nextLevelLastNode = node.left;
            }
            if (node.right != null) {
                queue.offer(node.right);
                nextLevelLastNode = node.right;
            }
            if (node == currLevelLastNode) {
                // 遍历完当前层所有的节点。层数+1
                maxDepth++;
                // 进入下一层
                currLevelLastNode = nextLevelLastNode;
                nextLevelLastNode = null;
            }
        }
        return maxDepth;
    }

    /**
     * 递归（推荐使用）
     * <p>
     * 终止条件： 当进入叶子节点后，再进入子节点，即为空，没有深度可言，返回0.<br>
     * 返回值： 每一级按照上述公式，返回两边子树深度的最大值加上本级的深度，即加1.<br>
     * 本级任务： 每一级的任务就是进入左右子树，求左右子树的深度。<br>
     *
     * <p>
     * <b>具体做法：</b><br>
     * step 1：对于每个节点，若是不为空才能累计一次深度，若是为空，返回深度为0.<br>
     * step 2：递归分别计算左子树与右子树的深度。<br>
     * step 3：当前深度为两个子树深度较大值再加1。<br>
     * </p>
     * </p>
     */
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth2(root.left), maxDepth2(root.right)) + 1;
    }


    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        node1.left = new TreeNode(2);

        TreeNode node2 = new TreeNode(1);
        node2.left = new TreeNode(2);
        node2.right = new TreeNode(3);
        node2.left.left = new TreeNode(4);
        node2.right.right = new TreeNode(5);


        BM0028MaxDepth_S bm0028MaxDepth_s = new BM0028MaxDepth_S();
        System.out.println(bm0028MaxDepth_s.maxDepth(node1));
    }

}
